package __question

import (
	"fmt"
	"math"
)

/****************** 荷兰国旗问题 *********************/

// A 给定一个数n，和数组l，将<=n的数放左边，大于n的数放右边
// 思路：定义边界区为-1，遍历数组，与n比较
// 如果 <= n, 将该数与边界区的后一个数交换，边界区+1
// 如果 > n, 什么都不做
// 举例：n = 5，list=[2, 6, 7, 5, 9, 3]
// 结果：list=[2, 5, 3, 6, 9, 7]
// 与快速排序很接近
func A(list []int, n int) int {
	x := -1
	for i := 0; i < len(list); i++ {
		if list[i] <= n {
			list[i], list[x+1] = list[x+1], list[i]
			x++
		}
	}
	return x
}

// B 给定一个数n，和数组l，将小于n的数放左边，等于n的数放中间，大于n的数放右边
// 思路：定义边界区i,j，从头遍历数组，与n比较
// if list[i] < n, 将该数与边界区i的后一个数交换，i++,k++
// if list[i] == n, k++, 继续
// if list[i] > n, 将该数与边界区j的前一个数交换，k不变，j--
// 举例：n = 5，list=[2, 6, 7, 5, 9, 3]
// [2, 3, 7, 5, 9, 6]
// [2, 3, 9, 5, 7, 6]
// [2, 3, 7, 5, 9, 6]
// 结果：list=[2, 3, 5, 9, 7, 6], 返回2，2
func B(list []int, n int) (int, int) {
	i, j := -1, len(list)
	k := 0
	for k < j && k < len(list) {
		if list[k] < n {
			list[k], list[i+1] = list[i+1], list[k]
			i++
			k++
		} else if list[k] > n {
			list[k], list[j-1] = list[j-1], list[k]
			j--
		} else {
			k++
		}
	}
	return i + 1, j - 1
}

/****************** 链表问题 *********************/

// SwapArray 前后对调数组元素
// [1, 2, 3] - > [3, 2, 1]
// [1, 2, 3, 4] - > [4, 3, 2, 1]
// 思路：单向遍历即可
func SwapArray(list []int) {
	n := len(list)
	if n <= 1 {
		return
	}
	for i := 0; i <= n>>1; i++ {
		head := i
		tail := n - i - 1
		if head >= tail {
			break
		}
		list[head], list[tail] = list[tail], list[head]
	}
}

// Node 单向链表
type Node struct {
	data int
	next *Node
}

// ReverseNode 反转单链表
// 思路1：缓存上一个，当前和下一个,因为是单向的
// begin mid end
// 	nil	<- A -> B -> C
// A <- B <- C
// 思路2：新建一个头结点，遍历的时候指向头节点即生成新的链表
func ReverseNode(node *Node) *Node {
	if node == nil || node.next == nil {
		return node
	}
	// 缓存三个
	var begin *Node
	mid := node
	end := node.next
	for {
		// 反转指针
		mid.next = begin
		// 判断
		if end == nil {
			break
		}
		// 向后移动
		begin = mid
		mid = end
		end = end.next
	}
	return mid
}

// DoubleNode 双向链表
type DoubleNode struct {
	data int
	prev *DoubleNode
	next *DoubleNode
}

// ReverseDoubleNode 反转双向链表
// 思路：缓存向前的指针即可，向后的本来就有
// 1 2 3 4
func ReverseDoubleNode(node *DoubleNode) *DoubleNode {
	if node == nil || node.next == nil {
		return node
	}
	var tmp *DoubleNode
	curr := node
	for curr.next != nil {
		// 交换指针
		tmp = curr.next
		curr.next = curr.prev
		curr.prev = tmp
		// 指向下一个
		curr = tmp
	}
	// 处理最后一个指针
	curr.next = curr.prev
	curr.prev = nil
	return curr
}

// PrintCommonsNode 打印两个有序链表的公共部分
// 给定头节点，头节点不包含数据
// 思路：同时遍历，谁小谁移动，直到相等打印，打印的下一步是同时移动，直到某个链表遍历完成
// [1, 3, 5, 7]
// [2, 3, 5, 8]
// 输出：3，5
func PrintCommonsNode(head1, head2 *Node) {
	if head1 == nil || head2 == nil {
		return
	}
	for head1.next != nil && head2.next != nil {
		data1 := head1.next.data
		data2 := head2.next.data
		if data1 < data2 {
			head1 = head1.next
		} else if data1 > data2 {
			head2 = head2.next
		} else {
			fmt.Print(data1)
			head1 = head1.next
			head2 = head2.next
		}
	}
}

//3.判断回文单链表
//1->2->2->1
//1->2->3->2->1
// A:栈结构 B：快慢指针，慢的走一位，快的走两位

// Atoi 4.将字符串转成数字，默认只会传包含数字的字符串
// 比如："1234" -> 1234
func Atoi(s string) int {
	n := len(s)
	numArr := make([]rune, n)
	for i, r := range s {
		// n=10, 9-0
		numArr[n-1-i] = r - 48
	}
	// 4321
	// 4*10^0 + 3*10^1 + 2*10^2 + 1*10^3
	var num rune
	for i, x := range numArr {
		p := math.Pow(10, float64(i))
		num += x * rune(p)
	}
	return int(num)
}
